/**
 * @ClassName Load
 * @Description TODO
 * @Author Quentin_zyj
 * @Date 2021/11/3 14:20
 */
public class Load {
    // 集装箱数
    static int n;
    // 当前载重量
    static int cw = 0;
    // 最优载重重量
    static int bestw = 0;
    // 剩余集装箱重量, 在算法运行前要初始化为所有w[i]的和
    static int r;
    // 第一艘轮船的载重量
    static int c1;
    // 第二艘轮船的载重量
    static int c2;
    // 当前解
    static int[] x;
    // 当前最优解
    static int [] bestx;
    // 集装箱重量数组
    static int [] w;

    /**
     *
     * @param i 搜索第i层
     */
    public static void back(int i) {
        if (i > n) {
            if (cw > bestw) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestw = cw;
            }
            return;
        }
        // 搜索子树
        r -= w[i];
        // 搜索左子树
        if (cw + w[i] <= c1) {
            x[i] = 1;
            cw += w[i];
            back(i+1);
            cw -= w[i];
        }
        // 搜索右子树
        // 限界
        if (cw + r > bestw) {
            x[i] = 0;
            back(i + 1);
        }
        r += w[i];
    }
}
